package leetcode.list;

import utils.node.ListNode;

import java.util.PriorityQueue;

/**
 * @Description: https://leetcode.cn/problems/merge-k-sorted-lists/
 * 给你一个链表数组，每个链表都已经按升序排列。
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 * @Author Ammar
 * @Create 2023/5/3 11:38
 */
public class _23_合并K个升序链表 {

    // 分治策略 时间复杂度O(nlogk)  空间复杂度O(1)
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        int step = 1;
        while (step < lists.length) { // 时间复杂度O(logk)
            for (int i = 0; i + step < lists.length; i += step * 2) { // 时间复杂度O(n)
                lists[i] = mergeTwoLists(lists[i], lists[i + step]);
            }
            step = step * 2;
        }
        return lists[0];
    }


    // 优先级队列 时间复杂度O(nlogk)  空间复杂度O(k)
    public static ListNode mergeKLists2(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        ListNode head = new ListNode(0);
        ListNode cur = head;

        // 将所有链表的头节点放入优先级队列(小顶堆) 时间复杂度O(k)
        PriorityQueue<ListNode> queue = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode node : lists) {
            if (node != null) queue.offer(node); // 时间复杂度O(logk)
        } // klogk

        // 每次取出最小的节点，然后将该节点的next节点放入优先级队列 时间复杂度O(n)
        while (!queue.isEmpty()) {
            ListNode node = queue.poll();
            cur.next = node;
            cur = cur.next;
            if (node.next != null) queue.offer(node.next);
        } // nlogk
        return head.next;
    }


    public static ListNode mergeKLists1(ListNode[] lists) {
        if (lists.length == 0) return null;
        if (lists.length == 1) return lists[0];
        ListNode mergedList = mergeTwoLists(lists[0], lists[1]);
        for (int i = 2; i < lists.length; i++) {
            mergedList = mergeTwoLists(mergedList, lists[i]);
        }
        return mergedList;
    }

    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 如果左链表为空
        if (list1 == null) return list2;
        if (list2 == null) return list1;

        ListNode li = list1; // 要比较的左节点
        ListNode ri = list2; // 要比较的右节点
        ListNode listRoot = list2; // 合成链表的root
        ListNode listIndex = null; // 指向合成链表中的刚插入的节点

        // 第一次比较
        if (li.val < ri.val) {
            ListNode node = li; // 胜出node
            li = li.next;
            node.next = listRoot;
            listRoot = node;
            listIndex = node;
        } else {
            ri = ri.next;
            listIndex = listRoot;
        }

        while (li != null && ri != null) {
            if (li.val < ri.val) {
                ListNode node = li;
                li = li.next;
                // 将左链表的 node 节点插入 listIndex 的 next
                node.next = listIndex.next;
                listIndex.next = node;
            } else {
                ri = ri.next;
            }
            listIndex = listIndex.next;
        }
        // 左链表没有元素了也不用做任何操作
        // 右链表没有元素了
        if (ri == null) {
            // 将左链表的所有元素移动到listIndex.next
            listIndex.next = li;
        }
        return listRoot;
    }
}
